package algorithm.leetcode.I101to200;

import java.util.HashMap;
import java.util.Map;

public class Q146 {

    public static void main(String[] args) {
        Map<String, Object> reqMsg = new HashMap<>();

        String shopCode = "111";
        if (reqMsg.get("shopCode") != null) shopCode = String.valueOf(reqMsg.get("shopCode"));
        System.out.println(shopCode);
    }

}


class LRUCache {

    static class InnerNode {
        int key, value;
        InnerNode prev, next;

        public InnerNode() {
        }

        public InnerNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final Map<Integer, InnerNode> cache = new HashMap<Integer, InnerNode>();
    private int size;
    private final int capacity;
    private final InnerNode head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        // 使用伪头部和伪尾部节点
        this.head = new InnerNode();
        this.tail = new InnerNode();
        // 伪头尾相连
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        InnerNode node = cache.get(key);

        // 如果不存在返回-1
        if (node == null) return -1;

        // 如果存在,取出值,并且把这个值插入到头部
        move2Head(node);
        return node.value;
    }

    public void put(int key, int value) {
        InnerNode node = cache.get(key);

        // 如果哈希表中没有,那么添加进哈希表,添加到链表,移动到头部,若超限执行删除最早使用
        if (node == null) {
            InnerNode innerNode = new InnerNode(key, value);
            add2Head(innerNode);
            cache.put(key, innerNode);
            size += 1;
            while (size > capacity) removeTail();
        }

        // 如果哈希表中有,那么替换原值,链表移动到头部
        else {
            node.value = value;
            move2Head(node);

        }

    }

    private void move2Head(InnerNode n) {
        // 可以画个图演示下这个过程,首先删除这个节点,然后添加到头部
        removeNode(n);
        add2Head(n);
    }

    private void removeNode(InnerNode n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }

    private void add2Head(InnerNode n) {
        head.next.prev = n;
        n.next = head.next;
        head.next = n;
        n.prev = head;
    }

    private void removeTail() {
        if (size > 0) {
            InnerNode noUseNode = tail.prev;
            removeNode(noUseNode);
            cache.remove(noUseNode.key);
            size -= 1;
        }
    }

}